package top.likeqc.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @see <a href="https://leetcode.cn/problems/next-greater-node-in-linked-list">1019.
 *     链表中的下一个更大节点</a>
 */
public class NextGreaterNodeInLinkedList {
    public static void main(String[] args) {
        Solution solution = new NextGreaterNodeInLinkedList().new Solution();
    }
    // leetcode submit region begin(Prohibit modification and deletion)
    /**
     * Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode()
     * {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val;
     * this.next = next; } }
     */
    class Solution {
        public int[] nextLargerNodes(ListNode head) {
            List<Integer> list = new ArrayList<>();
            ListNode p1, p2;
            p1 = head;
            while (p1 != null) {
                int t = p1.val;
                p2 = p1.next;
                while (p2 != null && p2.val <= t) {
                    p2 = p2.next;
                }

                list.add(p2 != null ? p2.val : 0);
                p1 = p1.next;
            }

            int[] ans = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                ans[i] = list.get(i);
            }
            return ans;
        }
    }
    // leetcode submit region end(Prohibit modification and deletion)

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {}

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
